1. Technical Field
The present invention relates to a cache memory for data storage in general and, in particular, to a cache memory having multiple cache-line replacement schemes. Still more particularly, the present invention relates to a cache memory having a selectable cache-line replacement scheme.
2. Description of the Prior Art
In conjunction with a system memory, a high-performance data-processing system typically also includes a cache memory. A cache memory is a small, high-speed memory that is interposed between a processor and the system memory of the data-processing system. A portion of the information, such as data or instructions, stored in the system memory may be copied into the cache memory so that this information will be available to the processor in a shorter time than it would be from the system memory.
When the information requested by the processor cannot be found in the cache memory, i.e., a cache miss, the required information must be obtained from the system memory. In addition to the immediate usage by the processor, a copy of such information will also be placed into the cache memory for any future usage by the processor. This process of loading the requested information from the system memory to the cache memory is known as linefill. At this time, if the cache memory has been completely filled, some information already stored in the cache memory will have to be cast-out or invalidated in order to make room for the new information. Accordingly, it is important to have a strategy to decide what information already in the cache memory should be discarded such that the "hit" rate of the cache memory will not be adversely affected.
In terms of cache-line replacement schemes, there are at least two schemes that are commonly employed, namely, Random and Least Recently Used (LRU). A random replacement scheme allows information to be allocated uniformly within the cache memory while an LRU replacement scheme reduces the chance of throwing out information that may be needed by the processor again in due course. This makes use of a corollary of temporal locality: If recently used cache lines are likely to be utilized again, then the best candidate for disposal is the least recently used cache line.
The effectiveness of a cache-line replacement scheme typically depends on the type of application software running within the processor. In other words, one cache-line replacement scheme may work extremely well with one certain application software while producing only mediocre results with other application software. Hence, it is difficult for a prior-art cache memory having only one built-in cache-line replacement scheme to produce a consistently high "hit" ratio regardless of the type of application software running within the processor. Consequently, it would be desirable to provide a cache memory having a selectable cache-line replacement scheme such that different cache line replacement schemes can be selected to accommodate various types of application software.